package com.zsk.algorithm;

//连续子串最大和问题
//https://www.cnblogs.com/zhangdebin/p/5567884.html
public class MaxSon {
	public static void main(String[] args) {
		
		//1.连续加法解法
		int l[] = new int[] { 2, 3, -9, 3, 2, 1, -1, 5, -9, 1, 2, 3 };
		int s = 0;
		int max = 0;
		int len = l.length;
		for (int i = 1; i < len; i++) {
			s += l[i];
			if (s < 0) {
				s = 0;
			} else if (s > max) {
				max = s;
			}
		}
		System.out.println(max);

		int num[] = new int[] { 2, 3, -9, 3, 2, 1, -1, 5, -9, 1, 2, 3 };
		int maxnum = 0;
		int currentmax = 0;
		int begin = 0;
		int end = 0;
		for (int i = 0; i < num.length; i++) {
			if (currentmax <= 0) {
				currentmax = num[i];
				begin = i;
			} else
				currentmax += num[i];
			if (currentmax > maxnum) {
				maxnum = currentmax;
				end = i;
			}
		}
		System.out.println(maxnum);
		for (int i = begin; i < end + 1; i++)
			System.out.print(num[i] + " ");
		System.out.println();

		//2.动态规划解法
		// 首先local[i]表示以a[i]为结尾的子序列的最大的和，则global = max{local[0], ... , local[n-1]} 。
		// global即为答案。而local[i +
		// 1]只有两个选择，要不就是和之前的数字连在一起组成一个序列，或者自己a[i+1]独立组成一个序列，哪个大选哪个,local[i+1] = max{
		// a[i+1], local[i] + a[i+1] }.
		int local = num[0];
		int global = local;
		int lstart=0;
		int lend = 0;
		for (int i = 1; i < len; i++) {
			local = Math.max(num[i], local + num[i]);
			if (global < local) {
				lend = i;
			}
			if(num[i]>local + num[i]) {
				lstart=i+1;
			}
			global = Math.max(local, global);
			
		}

		System.out.println(global + ","+lstart+"-" + lend);
	}
}
